package pers.qianyu.month_202011.date_20201123;

/**
 * [重要] 完全背包问题
 * 518. 零钱兑换 II
 * https://leetcode-cn.com/problems/coin-change-2/
 * 优秀题解：https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-iihe-pa-lou-ti-wen-ti-dao-di-yo/
 *
 * @author mizzle rain
 * @date 2020-11-23 17:28
 */
public class ChangeTwo {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = dp[i] + dp[i - coin];
            }
        }
        return dp[amount];
    }

    public int change2(int amount, int[] coins) {
        int[][] dp = new int[coins.length + 1][amount + 1];
        for (int i = 0; i <= coins.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= coins.length; i++) {
            for (int k = 1; k <= amount; k++) {
                if (k < coins[i - 1]) {
                    dp[i][k] = dp[i - 1][k];
                    continue;
                }
                dp[i][k] = dp[i - 1][k] + dp[i][k - coins[i - 1]];
            }
        }
        return dp[coins.length][amount];
    }

    public static void main(String[] args) {
        int result = new ChangeTwo().change(5, new int[]{1, 2, 5});
        System.out.println("result = " + result);
    }
}
